Sea $A \in \real^{n \times n}$, se desea hallar una descomposici\'on de 
la matr\'iz $A$ en dos matrices, $Q, R \in \times^{n \times n}$ tales 
que $Q$ es ortonormal y $R$ es triangular superior. 
Si $A = QR$, el sistema $Ax = b$ puede resolverse de la siguiente forma:
$$Ax=b\;\Longleftrightarrow\; QRx=b\;\Longleftrightarrow\;
Q^{t}QRx = Q^{t}b\;\Longleftrightarrow\; Rx=Q^{t}b$$
Al ser $R$ triangular superior, este \'ultimo sistema puede resolverse 
en $O(n^{2})$.

\begin{theorem}
	Sea $A$ $\in \real^{n\times n}$ entonces existen matrices $Q$ y 
	$R$, tales que $Q$ es ortogonal, $R$ es triangular superior y vale 
	que $A = QR$.
	Si adem\'as $A$ es no singular, existen \'unicas $Q$ y $R$ tales 
	que $R$ tiene elementos positivos en la diagonal.
\end{theorem}

Dado que el producto de matrices ortonormales es una matriz ortonormal,
una forma razonable de encontrar esta factorizaci\'on es triangular
superiormente a $A$ multiplic\'andola por matrices ortonormales. 
Al considerar operaciones que conservan la norma (caracter\'istica de 
las matrices ortonormales), las rotaciones y las reflexiones surgen
como opciones interesantes. En esta idea se basan los dos m\'etodos
siguientes para encontrar la factorizaci\'on $QR$ de cualquier matriz
$A \in \real^{n\times n}$.

%~ \begin{remark}
Una ventaja de ambos m\'etodos es que son num\'ericamente muy estables.
%~ \end{remark}
%~ \begin{example}
La factorizaci\'on QR puede utilizarse para calcular autovalores y para 
resolver el problema de cuadrados m\'inimos.
%~ \end{example}

\subsection{Reflexiones de Householder}
%~ \par
Una \textsl{reflexi\'on de Householder} es una transformaci\'on que, 
dado un vector, lo refleja sobre un plano. 
Puede construirse de forma tal que al reflejar un vector (fijo) se 
anulen todas sus coordenadas menos una.

\paragraph{}
Para triangular una matr\'iz usando reflexiones, se obtiene un conjunto 
de matrices reflectoras ortogonales 
$Q_{(1)}Q_{(2)}\dots,Q_{(n-1)}$.
Al multiplicar $A$ por $Q_{(i)}$ se refleja la columna $i$ de forma tal 
de obtener ceros en $A_{i(i+1)}, \dots, A_{in}$.
Sea $x$ la primera columna, en la cual se desean obtener ceros excepto 
en la primera posici\'on, entonces $Q$ es tal que 
$Qx = y$, con $y^{T}=(\pm\|x\|_{2},0,\dots,0)$.
Como $\|x\|_{2}=\|y\|_{2}$, puede probarse la existencia y unicidad de 
$Q$. 
Adem\'as esta matr\'iz ser\'a $Q=I-2uu^{T}$ con
$\displaystyle u = \frac{x-y}{\|x-y\|_{2}}$.

\par
Para el resto de las columnas se construye $Q_{i}$ de forma an\'aloga 
pero analizando la submatriz inferior derecha de la nueva $A$, y luego 
completando la matriz obtenida con la identidad; obteniendo $Q_{i}$ que 
coloca ceros en la columna $i$, sin alterar lo anterior.

\paragraph{}
La matriz de tranformaci\'on $Q=I-2uu^{T}$ refleja todos los vectores 
respecto del subespacio ortogonal a $u$. 
Al construir $u$ se puede elegir el signo del vector $y$ de manera de 
evitar una cancelaci\'on con $x$ y reducir los errores de c\'alculos.
En la pr\'actica lo m\'as eficiente es nunca construir directamente la 
matriz $Q$, sino operar distribuyendo para no hacer el producto 
$uu^{T}$, con lo cual la factorizaci\'on tiene complejidad 
$\displaystyle O\left(\frac{2}{3}n^3 \right)$.

\subsection{Rotaciones de Givens}
Una matriz de rotaci\'on $P$ difiere de la matr\'iz identidad en a lo 
sumo cuatro elementos, que tienen la forma $p_{ii}=p_{jj}=cos(\theta)$
y $p_{ij}=-p_{ji}=sen(\theta)$ para alg\'un $\theta$ e $i\neq j$.
Para cualquier matriz de rotaci\'on $P$, $PA$ difiere de $A$ s\'olo en 
las filas $i$ y $j$. 
Adem\'as, para cualquier $j\neq i$ se puede encontrar un \'angulo 
$\theta$ tal que $PA$ tenga un elemento cero para $(PA)_{ij}$ . 
Toda matriz de rotaci\'on $P$ es ortogonal ya que por definici\'on 
$PP^{T}=I$.

\paragraph{}
Para obtener los ceros necesarios debajo de la diagonal de $A$ para 
triangularla, se multiplica $A$ por una matriz de rotaci\'on $Q_{(ik)}$
que rota el vector de la columna $i$ de $A$ de manera tal de colocar 
ceros en la coordenada $k$ (es decir en $A_{ik}$).
Se repite este procedimiento para cada coordenada del vector columna 
que se desee anular, y a su vez para cada columna.
La matriz $Q$ es el producto de todas las $Q_{(ik)}$ traspuesto, y 
sigue siendo ortogonal. $R$ es $R=Q^{T}A$.

\paragraph{}
Una ventaja sobre HouseHolder es que puede colocar ceros en posiciones 
espec\'ificas de una matriz alterando muy poco la estructura original, 
una propiedad \'util si por ejemplo se quiere trabajar con matrices 
esparsas o con la forma de Hessenberg. 
La complejidad del m\'etodo es 
$\displaystyle O\left(\frac{4}{3}n^3 \right)$. 
